/**
 * 堆（优先队列）实现类
 * 支持最大堆和最小堆，通过比较函数控制堆类型
 */
class Heap {
  /**
   * 构造函数
   * @param {Function} compare 自定义比较函数，决定堆类型（最大堆/最小堆）
   * 不传时默认最小堆：(a, b) => a - b
   */
  constructor(compare) {
    // 使用数组存储堆元素
    this.heap = []

    // 保存原始比较函数，如果未提供则使用默认最小堆比较函数
    const originCompare = compare || ((a, b) => a - b)

    /**
     * 实际使用的比较函数（对原始比较结果取反）
     * 这样设计是为了保持堆操作方法的统一逻辑
     * @param {*} a 第一个比较元素
     * @param {*} b 第二个比较元素
     * @returns 比较结果，如果结果为NaN则返回0
     */
    this.compare = (a, b) => {
      const res = -originCompare(a, b)  // 关键：对比较结果取反
      return isNaN(res) ? 0 : res       // 如果比较结果是 NaN （例如比较 undefined ），则返回 0
    }
  }

  /**
   * 获取堆中元素数量
   * @returns {number} 堆大小
   */
  size() {
    return this.heap.length
  }

  /**
   * 判断堆是否为空
   * @returns {boolean} 是否为空
   */
  isEmpty() {
    return this.heap.length === 0
  }

  /**
   * 向堆中添加元素
   * @param {*} value 要添加的值
   */
  push(value) {
    this.heap.push(value)               // 将新元素添加到数组末尾
    this.bubbleUp(this.heap.length - 1) // 执行上浮操作维护堆结构
  }

  /**
   * 移除并返回堆顶元素
   * @returns {* | undefined} 堆顶元素或undefined（堆为空时）
   */
  pop() {
    if (this.isEmpty()) return undefined  // 空堆检查

    const top = this.heap[0]      // 保存堆顶元素

    const last = this.heap.pop()  // 移除并保存最后一个元素

    if (!this.isEmpty()) {
      this.heap[0] = last         // 将最后一个元素移到堆顶
      this.sinkDown(0)            // 执行下沉操作维护堆结构
    }

    return top                    // 返回原堆顶元素
  }

  /**
   * 上浮操作（堆化）
   * 将指定位置的元素向上移动，直到满足堆性质
   * @param {number} index 需要上浮的元素索引
   */
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2) // 计算父节点索引

      // 如果当前节点比父节点"优先"（根据比较函数）
      if (this.compare(this.heap[index], this.heap[parentIndex]) > 0) {
        this._swap(index, parentIndex) // 交换两者位置
        index = parentIndex           // 继续向上检查
      } else break                    // 如果已满足堆性质，则停止
    }
  }

  /**
   * 下沉操作（堆化）
   * 将指定位置的元素向下移动，直到满足堆性质
   * @param {number} index 需要下沉的元素索引
   */
  sinkDown(index) {
    let current = index
    const length = this.size()

    while (true) {
      const left = 2 * current + 1    // 左子节点索引
      const right = 2 * current + 2  // 右子节点索引
      let target = current          // 初始化目标位置为当前位置

      // 检查左子节点是否更"优先"
      if (left < length && this.compare(this.heap[left], this.heap[target]) > 0)
        target = left

      // 检查右子节点是否比当前目标更"优先"
      if (right < length && this.compare(this.heap[right], this.heap[target]) > 0)
        target = right

      // 如果找到了更"优先"的子节点
      if (target !== current) {
        this._swap(current, target)  // 交换位置
        current = target            // 继续向下检查
      } else break                  // 如果已满足堆性质，则停止
    }
  }

  /**
   * 交换堆中两个元素的位置
   * @param {number} idx1 第一个元素的索引
   * @param {number} idx2 第二个元素的索引
   */
  _swap(idx1, idx2) {
    [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
  }
}

// 使用示例：创建最大堆
const maxpq = new Heap((a, b) => b - a)
maxpq.push(3)
maxpq.push(9)
maxpq.push(2)
maxpq.push(11)

// 依次弹出最大元素
console.log(maxpq.pop())
console.log(maxpq.pop())
console.log(maxpq.pop())
console.log(maxpq.pop())